/* Copyright (C) 2007 Free Software Foundation, Inc. 
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/6/5.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 238. 除自身以外数组的乘积
 * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
 *
 * 示例:
 * 输入: [1,2,3,4]
 * 输出: [24,12,8,6]
 *
 * 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
 *
 * 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 *
 * 进阶：
 * 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
 */
#include <iostream>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>

using namespace std;

class Solution {
public:
    static vector<int> productExceptSelf(vector<int>& nums) {
        /* 初步思路：从左到右计算出第 i 个数的除外乘积，每 i+1 我们就除掉 i+1 本身，
         * 然后再乘与 i-1，就是 i+1 的结果了。但是...官方说不能用除法，这个方案就马
         * 上否决掉吧。
         *
         * 经过思考，不用乘法，又想要排除 i+1？就必须在计算的时候就要把 i+1 排除在外
         * 边，所以我决定使用一个指针 CURR，它指向计算的第 i 个数字，每次都以起始指针
         * START~CURR 作为左边要计算的乘积区域，以结束指针END，CURR+1~END作为右边
         * 的乘积区域，分别计算这两个区域的乘积，再一块相乘，自然就是排除掉了 i 的乘积
         * 啦，真棒，不愧是我～但问题来了，如果就这样初步实现，那么复杂度是 O(n^2)，不
         * 符合 O(n) 要求，一提交，果然，超时了，我们需要再优化。
         *
         * 从上面的思路来看，我们白白计算了很多次左右边的值，我们需要优化这里。第二次我
         * 们达到了要求，没有两层 for，复杂度到了 O(n)。
         *
         * 最后，官方的进阶任务，我想了半天暂时没想出来，之后想出来给它也解决掉。
         */

        /* 第一次实现，超时了 */
//        const int START = 0, END = nums.size();
//        vector<int> ans(END);
//        for(int CURR = START; CURR < END; ++CURR) {
//            int curr_ans = 1;
//            /* 先计算左区域 */
//            for(int left = START; left < CURR; ++left) {
//                curr_ans *= nums[left];
//            }
//            /* 现在是右区域 */
//            for(int right = CURR + 1; right < END; ++right) {
//                curr_ans *= nums[right];
//            }
//            ans[CURR] = curr_ans;
//        }

        /* 第二次实现，复杂度 O(n) */
        const int START = 0, END = nums.size();
        int CURR;
        vector<int> left_ans(END);
        int right_ans[END];
        /* 先计算左区域，不要重新算，直接用上次的乘积 */
        int LEFT_ANS = left_ans[START] = 1;
        for(CURR = START + 1; CURR < END; ++CURR) {
            LEFT_ANS *= nums[CURR - 1];
            left_ans[CURR] = LEFT_ANS;
        }

        /* 现在是右区域，不要重新算，直接用上次的乘积  */
        int RIGHT_ANS = right_ans[END - 1] = 1;
        for(CURR = END - 2; CURR >= START; --CURR) {
            RIGHT_ANS *= nums[CURR + 1];
            right_ans[CURR] = RIGHT_ANS;
        }

        /* 计算每个值的除外乘积 */
        for(CURR = START; CURR < END; ++CURR) {
            left_ans[CURR] *= right_ans[CURR];
        }

        return left_ans;
    }
};


int main() {

    vector<int> in = {1, 2, 3, 4};
    vector<int> ans = Solution::productExceptSelf(in);
    for(int i : ans) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

